import java.util.Iterator;
import java.util.NoSuchElementException;


/*
 * This class was implemented based primarily on the ArrayQueue.java example
 * provided by the instructor on blackboard. The main difference is this
 * is implements a random remove() function.
 * 
 * Author: C. Nathan Logan
 * Onyx login: clogan
 */

public class RandomizedQueue<Item> implements Iterable<Item>{

	private static int N; 		// number of items in queue
	private int head;			// beginning of queue
	private int tail;			// end of queue
	private Item[] items;		// Array for queue
	
	/**
	 * Constructs an empty RandomizedQueue
	 */
	public RandomizedQueue(){
		head = tail = 0;
		N = 0;
		items = (Item[]) new Object[2];
	}
	
	/**
	 * Returns true if RandomizedQueue is empty.
	 */
	public boolean isEmpty(){
		return N == 0;
	}
	
	/**
	 * Adds an item to the end of the RandomizedQueue.
	 * @param Item to be inserted at end of the RandomizedQueue.
	 */
	public void add(Item item){
		// If the queue array is full, the size of the array is doubled
		if(N==items.length){
			resize(N<<1);
		}
		
		// Adds the item and increments the tail pointer
		items[tail] = item;
		tail++;
		N++;
	}
	
	/**
	 * Removes and returns an item randomly from the RandomizedQueue.
	 * @return The item returned randomly from the RandomizedQueue.
	 */
	public Item remove(){
		// Gets and integer randomly between 0 and the size of the queue
		// using the StdRandom class provided by the instructor.
		int random = StdRandom.uniform(N);
		
		// Doesn't allow a remove on an empty queque.
		if(isEmpty()){
			throw new RuntimeException("Empty, cannot remove");
		}	
		// If the queue is one fourth the size of the array, the array is halved.
		if(N > 0 && N == items.length>>2){
			resize(items.length>>1);
		}
		
		/*
		 * This takes the randomly selected item and swaps it with the last item 
		 * in the RandomizedQueue, removes it from the queue by decrementing the 
		 * tail index, and returns the randomly selected item. This makes it so
		 * the array doesn't have to be re-organized every-time an item is removed
		 * from the middle of the array.
		 */
		Item ret = items[random];
		items[random] = items[tail-1];
		tail--;
		N--;
		return ret;
	}
	
	/**
	 * Return a string of all the elements in the queue.
	 */
	public String toString(){
		String out = "";
		for(int i=0; i<tail; i++){
			out = out + "" + items[i].toString() + "\n";
		}
		return out;
	}
	
	/**
	 * Return the size of the queue.
	 */
	public int size(){
		return N;
	}
	
	/*
	 * Implemented the resize method provided in the ArrayQueue.java example
	 * provided by the instructor.
	 */
	private void resize(int size){
		Item[] temp = (Item[]) new Object[size];
        int i = 0;
        int j = head;
        for (int k = 0; k < N; k++) 
        {
            temp[i] = items[j];
            i++;
            j = (j + 1) % items.length;
        }
        head = 0;
        tail = i;
        items = temp;
	}
	
	/** 
	 * Returns an iterator over the elements in the RandomizedQueue.
	 * Throws NoSuchElementException if you try to iterate over an
	 * empty RandomizedQueue.
     */
    public Iterator<Item> iterator() throws NoSuchElementException {
        return new QueueIterator();
    }
    
    /*
	 * NOTE: This iterator uses the SList example provided in
     * class on 9/14/2009 with a couple minor changes to make
     * it an array iterator.
	 */
    private class QueueIterator implements Iterator<Item>{
    	private int current;
    	
    	// Constructor sets current to first item in the RandomizedQueue
    	public QueueIterator(){
    		current = head;
    	}
    	
    	// Checks if there is another object in the RandomizedQueue
    	public boolean hasNext(){
    		return current < tail;
    	}
    	
    	// Returns the next object and moves the pointer current to the next item
    	// if there is another one in the RandomizedQueue
    	public Item next() throws NoSuchElementException {
    		// Throws an exception if you try to iterate over an empty RandomizedQueue
    		if(current >= tail){
    			throw new NoSuchElementException("No item to return");
    		}
    		Item it = null;
			if(hasNext()){
				it = items[current];
				current++;
			}
			return it;
    	}
    	
    	// Not supported
    	public void remove(){
			throw new RuntimeException("Not supported");
		}
    }

	
	// Main method used for testing
	public static void main(String[] args) {
		RandomizedQueue<String> test = new RandomizedQueue<String>();
		
		test.add("Nathan");
		test.add("Cody");
		test.add("Wayne");
		test.add("Kris");
		
		StdOut.println("Queue: \n" + test.toString());
		StdOut.println("Queue size: " + test.size());
		System.out.println();
		StdOut.println("Item removed: " + test.remove());
		System.out.println();
		StdOut.println("New queue: \n" + test.toString());
		StdOut.println("New queue size: " + test.size());
		
		RandomizedQueue<String> test2 = new RandomizedQueue<String>();
		
		test2.add("Nathan");
		test2.add("Cody");
		StdOut.println("Queue2 size: " + test2.size());
		
		Iterator<String> t = test.iterator();
		String s = "[  ";
	    
	    for (; t.hasNext(); ) 
	    {
	        s = s + t.next() + "  ";
	    }
	    s = s + "]";
	    
	    StdOut.println(s);
	    
	    RandomizedQueue<String> test3 = new RandomizedQueue<String>();
	    t = test3.iterator();
	    StdOut.println(t.hasNext());
	    //StdOut.println(t.next());
	    //test3.remove();
		

	}

}
